{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Additive Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isAdditiveNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #累加数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>累加数</strong> 是一个字符串，组成它的数字可以形成累加序列。</p>\n",
    "\n",
    "<p>一个有效的 <strong>累加序列</strong> 必须<strong> 至少 </strong>包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。</p>\n",
    "\n",
    "<p>给你一个只包含数字&nbsp;<code>'0'-'9'</code>&nbsp;的字符串，编写一个算法来判断给定输入是否是 <strong>累加数</strong> 。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><strong>说明：</strong>累加序列里的数，除数字 0 之外，<strong>不会</strong> 以 0 开头，所以不会出现&nbsp;<code>1, 2, 03</code> 或者&nbsp;<code>1, 02, 3</code>&nbsp;的情况。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>\"112358\"</code>\n",
    "<strong>输出：</strong>true \n",
    "<strong>解释：</strong>累加序列为: <code>1, 1, 2, 3, 5, 8 </code>。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入<code>：</code></strong><code>\"199100199\"</code>\n",
    "<strong>输出：</strong>true \n",
    "<strong>解释：</strong>累加序列为: <code>1, 99, 100, 199。</code>1 + 99 = 100, 99 + 100 = 199</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 35</code></li>\n",
    "\t<li><code>num</code> 仅由数字（<code>0</code> - <code>9</code>）组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你计划如何处理由过大的整数输入导致的溢出?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [additive-number](https://leetcode.cn/problems/additive-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [additive-number](https://leetcode.cn/problems/additive-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"112358\"', '\"199100199\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        def dfs(i):\n",
    "            if len(ans) >= 3 and ans[-1] != ans[-2] + ans[-3]:\n",
    "                return False\n",
    "            if i == n:\n",
    "                return len(ans) >= 3\n",
    "            for j in range(i, len(num)):\n",
    "                if num[i:j+1].startswith('0') and len(num[i:j+1]) > 1:\n",
    "                    continue\n",
    "                ans.append(int(num[i:j+1]))\n",
    "                if dfs(j+1):\n",
    "                    return True\n",
    "                ans.pop()\n",
    "            return False\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def dfs(past1, past2, i):\n",
    "            if i==len(num):\n",
    "                return True\n",
    "            \n",
    "            tmp = past1+past2\n",
    "            next_num = str(tmp)\n",
    "            if next_num==num[i:i+len(next_num)]:\n",
    "                return dfs(past2, tmp, i+len(next_num))\n",
    "            return False\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(len(num)-2):\n",
    "            for j in range(i+1, len(num)-1):\n",
    "                if not (num[0]=='0' and i>0) and not (num[i+1]=='0' and (j-i)>1):\n",
    "                    num1 = int(num[:i+1])\n",
    "                    num2 = int(num[i+1:j+1])\n",
    "                    flag = flag or dfs(num1, num2, j+1)\n",
    "                    # print(flag, i, j)\n",
    "        return flag\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveSeq(self, num:str, second:str, third:str) -> bool:\n",
    "        if second[0] == '0' and int(second) != 0:\n",
    "            return False\n",
    "        if third[0] == '0' and int(third) != 0:\n",
    "            return False\n",
    "        n = len(num)\n",
    "        if n == 0:\n",
    "            return True\n",
    "        res = False\n",
    "        for i in range(n):\n",
    "            if num[i] == '0' and int(num[i:]) != 0:\n",
    "                continue\n",
    "            if int(num[i:]) + int(second) == int(third) \\\n",
    "            and self.isAdditiveSeq(num[:i], num[i:], second):\n",
    "                res = True\n",
    "                break\n",
    "        return res\n",
    "\n",
    "\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        res = False\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1, n):\n",
    "                if self.isAdditiveSeq(num[:i], num[i:j], num[j:]):\n",
    "                    res = True\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        for i in range(1, len(num) - 1):\n",
    "            for j in range(i + 1, len(num)):\n",
    "                last, first, second = 0, i, j\n",
    "                while second < len(num):\n",
    "                    if (num[last] == '0' and first > last + 1) or (num[first] == '0' and second > first + 1) or len(num) - second < second - first:\n",
    "                        break\n",
    "                    s = str(int(num[last:first]) + int(num[first:second]))\n",
    "                    if s != num[second:second+len(s)]:\n",
    "                        break\n",
    "                    last, first, second = first, second, second + len(s)\n",
    "                else:\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        list1=list()\n",
    "        list2=list()\n",
    "        def judge(s,i):\n",
    "            if i>=3:\n",
    "                if list1[i-3]+list1[i-2]!=list1[i-1]:\n",
    "                    return\n",
    "            if len(s)==0:\n",
    "                if len(list1)<3:\n",
    "                    return\n",
    "                else:\n",
    "                    list2.append(list1[:])\n",
    "                    return\n",
    "            if s[0]==\"0\":\n",
    "                number=int(s[0])\n",
    "                list1.append(number)\n",
    "                judge(s[1:],i+1)\n",
    "                list1.pop()\n",
    "            else:\n",
    "                for k in range(0,len(s)):\n",
    "                    number = int(s[0:k+1])\n",
    "                    s1 = s[k+1:]\n",
    "                    list1.append(number)\n",
    "                    judge(s1, i + 1)\n",
    "                    list1.pop()\n",
    "                \n",
    "        judge(num,0)\n",
    "        if len(list2)!=0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        if n < 3: return False\n",
    "        def check(p1, p2, j):\n",
    "            while j < n:\n",
    "                p = str(int(p1) + int(p2))\n",
    "                if num[j: j+len(p)] != p:\n",
    "                    return False\n",
    "                j += len(p)\n",
    "                p1, p2 = p2, p\n",
    "            return True\n",
    "        for i in range(1, n//2+1) if num[0] != \"0\" else [1]:\n",
    "            for j in range(i+1, n) if num[i] != \"0\" else [i+1]:\n",
    "                p1 = num[:i]\n",
    "                p2 = num[i:j]\n",
    "                if check(p1, p2, j):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        if len(num) < 3:\n",
    "            return False\n",
    "        self.res = False\n",
    "        def backTrack(rest, tmp_cnt, last1, last2):\n",
    "            if tmp_cnt <= 2 and not rest:\n",
    "                return \n",
    "            if not rest:\n",
    "                self.res = True \n",
    "                return \n",
    "            \n",
    "            for i in range(len(rest)):\n",
    "                if len(rest[:i+1]) != len(str(int(rest[:i+1]))):\n",
    "                    return \n",
    "                if tmp_cnt >= 2:\n",
    "                    if int(rest[:i+1]) == last1 + last2:\n",
    "                        backTrack(rest[i+1:], tmp_cnt + 1, last2, int(rest[:i+1]))\n",
    "                else:\n",
    "                    backTrack(rest[i+1:], tmp_cnt + 1, last2, int(rest[:i+1]))\n",
    "                if self.res:\n",
    "                    return \n",
    "        backTrack(num, 0, 0, 0)\n",
    "        return self.res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        # 类似于回溯\n",
    "        # 字符串加法\n",
    "\n",
    "        ord_0 = ord('0')\n",
    "\n",
    "        def string_add(str1, str2):\n",
    "            ans = list()\n",
    "            carry = 0  # 进位\n",
    "            str1 = list(str1)\n",
    "            str2 = list(str2)\n",
    "\n",
    "            while str1 or str2:\n",
    "                if str1:\n",
    "                    a = str1.pop()\n",
    "                else:\n",
    "                    a = '0'\n",
    "                if str2:\n",
    "                    b = str2.pop()\n",
    "                else:\n",
    "                    b = '0'\n",
    "\n",
    "                temp = ord(a) + ord(b) + carry - 2 * ord_0  # int\n",
    "                # print(a, b, carry)\n",
    "                carry = temp // 10\n",
    "                ans.append(str(temp % 10))\n",
    "\n",
    "            if carry > 0:\n",
    "                ans.append(str(carry % 10))\n",
    "            return ''.join(ans[::-1])\n",
    "\n",
    "\n",
    "        def valid(b_start, b_end):\n",
    "            a_start = 0\n",
    "            a_end = b_start - 1\n",
    "\n",
    "            while b_end <= n - 1:\n",
    "                c = string_add(num[a_start: a_end + 1], num[b_start: b_end + 1])\n",
    "                # print(num[a_start: a_end+1], num[b_start: b_end+1], c)\n",
    "                c_start = b_end + 1\n",
    "                c_end = c_start + len(c) - 1\n",
    "                if c_end >= n or c != num[c_start: c_end + 1]:\n",
    "                    return False\n",
    "                \n",
    "                if c_end == (n - 1):\n",
    "                    return True\n",
    "\n",
    "                a_start, a_end = b_start, b_end\n",
    "                b_start, b_end = c_start, c_end\n",
    "\n",
    "\n",
    "        # 前两个数字最重要\n",
    "        n = len(num)\n",
    "        # first_start = 0, first_end - second_start = -1\n",
    "        for second_start in range(1, n-1):  # 至少有三个数字\n",
    "            if num[0] == '0' and second_start != 1:\n",
    "                continue\n",
    "\n",
    "            for second_end in range(second_start, n-1):\n",
    "                if num[second_start] == '0' and second_end != second_start:\n",
    "                    continue\n",
    "                \n",
    "                if valid(second_start, second_end):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        L = len(num)\n",
    "        if L < 3: return False\n",
    "        if all(c=='0' for c in num): return True\n",
    "        for i in range(1,(L+1)//2):\n",
    "            if num[0] == '0' and i > 1: continue\n",
    "            A = int(num[:i])\n",
    "            for j in range(1,(L-i)//2+1):\n",
    "                if num[i] == '0' and j > 1 or num[i+j] == '0': continue\n",
    "                B = int(num[i:i+j])\n",
    "                #print('start with:',a,b)\n",
    "                a,b = A,B\n",
    "                k = i+j\n",
    "                while 1:\n",
    "                    c = a+b\n",
    "                    #print(a,b,c)\n",
    "                    s = str(c)\n",
    "                    l = len(s)\n",
    "                    if k+l > L or s != num[k:k+l]: break\n",
    "                    k += l\n",
    "                    if k == L: return True\n",
    "                    a,b = b,c\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        if len(num) < 3:\n",
    "            return False\n",
    "        n = len(num)\n",
    "        for i in range(n-1):\n",
    "            s1 = num[:i+1]\n",
    "            if len(s1) > 1 and s1.startswith('0'):\n",
    "                break\n",
    "            for j in range(i+1, n):\n",
    "                s2 = num[i+1: j+1]\n",
    "                if len(s2) > 1 and s2.startswith('0'):\n",
    "                    break\n",
    "                n1, n2 = int(s1), int(s2)\n",
    "                # print(n1, n2)\n",
    "                k = j+1\n",
    "                if k == n:\n",
    "                    continue\n",
    "                while k < n:\n",
    "                    n3 = n1+n2\n",
    "                    l = len(str(n3))\n",
    "                    # print(n1, n2, n3, k, num[k:k+l])\n",
    "                    if num[k: k+l] != str(n3):\n",
    "                        break\n",
    "                    k += l\n",
    "                    n1, n2 = n2, n3\n",
    "                if k == n:\n",
    "                    return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def check(a,b):\n",
    "            if a.startswith('0') and a!='0' or b.startswith('0') and b!='0' :\n",
    "                return False\n",
    "            temp = a + b\n",
    "            while len(temp)<len(num):\n",
    "                a,b = b,str(int(a)+int(b))\n",
    "                temp += b\n",
    "            return temp == num\n",
    "        for i in range(1,len(num)-1):\n",
    "            for j in range(i):\n",
    "                if  check(num[:j+1],num[j+1:i+1]):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if len(path) >= 3 and path[-1] != path[-2] + path[-3]:\n",
    "                return False\n",
    "            if i == n:\n",
    "                return len(path) >= 3\n",
    "            if num[i] == '0':\n",
    "                path.append(int(num[i]))\n",
    "                if (dfs(i + 1)):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            else:\n",
    "                x = 0\n",
    "                for j in range(i, n):\n",
    "                    x = x * 10 + int(num[j])\n",
    "                    path.append(x)\n",
    "                    if dfs(j + 1):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "\n",
    "            return False\n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def check(i, j, k):\n",
    "            if j-i > 1 and num[i] == '0' or k-j > 1 and num[j] == '0':\n",
    "                return False\n",
    "            nxt = str(int(num[i:j]) + int(num[j:k]))\n",
    "            if not num[k:].startswith(nxt):\n",
    "                return k==n\n",
    "            return check(j, k, k+len(nxt))\n",
    "\n",
    "        n = len(num)\n",
    "        return any(check(0, i, j) for i in range(1, n-1) for j in range(i+1, n) )\n",
    "        # for i in range(1, n-1):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if check(0, i, j):\n",
    "        #             return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        if int(num)==0 and len(num)>=3:\n",
    "            return True\n",
    "        def dfs(first, second, left, depth):\n",
    "            if left=='':\n",
    "                if depth==2:\n",
    "                    return False\n",
    "                return True\n",
    "            sum_v = int(first)+int(second)\n",
    "            length = len(str(sum_v))\n",
    "            if left[0]=='0' or len(left)<length:\n",
    "                return False\n",
    "            if sum_v==int(left[:length]):\n",
    "                return dfs(second, left[:length], left[length:], depth+1)\n",
    "            return False\n",
    "        ans = False\n",
    "        for i in range(len(num)):\n",
    "            if num[0]=='0' and i!=0:\n",
    "                break\n",
    "            for j in range(i+1, len(num)):\n",
    "                if num[i+1]=='0' and j!=i+1:\n",
    "                    break\n",
    "                ans = ans or dfs(num[:i+1], num[i+1:j+1], num[j+1:], 2)\n",
    "                if ans:\n",
    "                    return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        if num[0] == '0' and len(num) < 3:\n",
    "                return False\n",
    "        for i in range(1,len(num)): # i前面的数字为第一个数\n",
    "            for j in range(i+1,len(num)): # i ： j为第二个数\n",
    "                t1 = int(num[:i])\n",
    "                t2 = int(num[i:j])\n",
    "                if len(num[i:j]) > 1 and num[i] == '0' or len(num[:i]) > 1 and num[0] == '0' :\n",
    "                    break\n",
    "                tstr = num[:j]\n",
    "                while num[len(tstr):].find(str(t1+t2)) == 0:\n",
    "                    tstr += str(t1+t2)\n",
    "                    t1,t2 = t2,t1+t2\n",
    "                if len(tstr) == len(num):\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        ans = False\n",
    "        path = []\n",
    "        n = len(num)\n",
    "        def dfs(u):\n",
    "            nonlocal ans\n",
    "            if u == n:\n",
    "                if len(path) >= 3:\n",
    "                    ans = True\n",
    "                return\n",
    "            for j in range(u, n):\n",
    "                seq = int(num[u:j+1])\n",
    "                if str(seq) != num[u:j+1]:\n",
    "                    break\n",
    "                if len(path) >= 2 and path[-2] + path[-1] != seq:\n",
    "                    continue\n",
    "                path.append(seq)\n",
    "                dfs(j + 1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def isValid(i,j):\n",
    "            last_index=0\n",
    "            while j <= n-2:\n",
    "                first_num = int(num[last_index:i+1])\n",
    "                if i+1-last_index >= 2 and num[last_index]=='0':\n",
    "                    return False\n",
    "                second_num = int(num[i+1:j+1])\n",
    "                if j-i >= 2 and num[i+1]=='0':\n",
    "                    return False\n",
    "                third_num = str(first_num+second_num)\n",
    "                len_third = len(third_num)\n",
    "\n",
    "                last_index = i+1\n",
    "                i = j\n",
    "                j = j+len_third\n",
    "\n",
    "                third_num_ori = num[i+1:j+1]\n",
    "                if j<=n-1 and third_num==third_num_ori:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            if j==n-1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "\n",
    "        last_num = 0\n",
    "        n=len(num)\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1,n-1):\n",
    "                if isValid(i,j):\n",
    "                    return True\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "        return False\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def dfs(idx, num1, num2):\n",
    "            if idx == len(num):\n",
    "                return True\n",
    "            \n",
    "            next_num = str(int(num1) + int(num2))\n",
    "            if not num.startswith(next_num, idx):\n",
    "                return False\n",
    "            \n",
    "            return dfs(idx + len(next_num), num2, next_num)\n",
    "        \n",
    "        n = len(num)\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1, n):\n",
    "                num1, num2 = num[:i], num[i:j]\n",
    "                if (len(num1) > 1 and num1[0] == '0') or (len(num2) > 1 and num2[0] == '0'):\n",
    "                    continue\n",
    "                if dfs(j, num1, num2):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        ans=False\n",
    "        def dfs(i,tmp):\n",
    "            nonlocal ans\n",
    "            if ans:\n",
    "                return\n",
    "            if i==n and len(tmp)>=3:\n",
    "                ans=True\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                if int(num[i])==0 and j>i:\n",
    "                    break\n",
    "                w=num[i:j+1]\n",
    "                if len(tmp)<2 or int(w)==tmp[-1]+tmp[-2]:\n",
    "                    tmp.append(int(w))\n",
    "                    dfs(j+1,tmp)\n",
    "                    tmp.pop()\n",
    "        dfs(0,[])\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        for secondStart in range(1, n-1):\n",
    "            if num[0] == '0' and secondStart != 1:\n",
    "                break\n",
    "            for secondEnd in range(secondStart, n-1):\n",
    "                if num[secondStart] == '0' and secondStart != secondEnd:\n",
    "                    break\n",
    "                if self.valid(secondStart, secondEnd, num):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def valid(self, secondStart: int, secondEnd: int, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        firstStart, firstEnd = 0, secondStart - 1\n",
    "        while secondEnd <= n - 1:\n",
    "            third = self.stringAdd(num, firstStart, firstEnd, secondStart, secondEnd)\n",
    "            thirdStart = secondEnd + 1\n",
    "            thirdEnd = secondEnd + len(third)\n",
    "            if thirdEnd >= n or num[thirdStart:thirdEnd+1] != third:\n",
    "                break\n",
    "            if thirdEnd == n-1:\n",
    "                return True\n",
    "            firstStart, firstEnd = secondStart, secondEnd\n",
    "            secondStart, secondEnd = thirdStart, thirdEnd\n",
    "        return False\n",
    "    \n",
    "    def stringAdd(self, s: str, firstStart: int, firstEnd: int, secondStart: int, secondEnd: int) -> str:\n",
    "        third = []\n",
    "        carry, cur = 0, 0\n",
    "        while firstEnd >= firstStart or secondEnd >= secondStart or carry != 0:\n",
    "            cur = carry\n",
    "            if firstEnd >= firstStart:\n",
    "                cur += ord(s[firstEnd]) - ord('0')\n",
    "                firstEnd -= 1\n",
    "            if secondEnd >= secondStart:\n",
    "                cur += ord(s[secondEnd]) - ord('0')\n",
    "                secondEnd -= 1\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            third.append(chr(cur + ord('0')))\n",
    "        return ''.join(third[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        flag = False\n",
    "        def dfs(u, st):\n",
    "            nonlocal flag\n",
    "            if u == n:\n",
    "                if len(ans) >= 3 and ans[-1] == ans[-2] + ans[-3]:\n",
    "                    flag = True\n",
    "                return\n",
    "            if u - st + 1 >= 2 and num[st] == '0':\n",
    "                return\n",
    "            if u < n - 1:\n",
    "                dfs(u + 1, st)\n",
    "            a = int(num[st:u+1])\n",
    "            if len(ans) >= 2 and ans[-1] + ans[-2] == a:\n",
    "                ans.append(a)\n",
    "                dfs(u + 1, u + 1)\n",
    "                ans.pop()\n",
    "            if len(ans) < 2:\n",
    "                ans.append(a)\n",
    "                dfs(u + 1, u + 1)\n",
    "                ans.pop()\n",
    "        dfs(0, 0)\n",
    "        return flag\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "\n",
    "    # 回溯法来验证当前选择的数字是否能构成累加数\n",
    "        def backtrack(start, path):\n",
    "            # 如果序列大于3，并且已经遍历完整个字符串，则找到了累加序列\n",
    "            if len(path) >= 3 and start == length:\n",
    "                return True\n",
    "            \n",
    "            # 从start位置开始，尝试所有可能的数字\n",
    "            for end in range(start + 1, length + 1):\n",
    "                # 除0外，其他数字不应以0开始\n",
    "                if s[start] == \"0\" and end - start > 1:\n",
    "                    break\n",
    "                \n",
    "                num = int(s[start:end])\n",
    "                \n",
    "                # 如果path中的数字大于等于2，则需要验证当前数字是否为前两个数字的和\n",
    "                if len(path) >= 2:\n",
    "                    # 如果num大于path中最后两个数字的和，则不可能是累加序列\n",
    "                    if num > path[-1] + path[-2]:\n",
    "                        break\n",
    "                    # 如果num小于path中最后两个数字的和，则尝试下一个num\n",
    "                    elif num < path[-1] + path[-2]:\n",
    "                        continue\n",
    "                \n",
    "                # 回溯\n",
    "                \n",
    "                if backtrack(end, path+[num]):\n",
    "                    return True\n",
    "                \n",
    "            return False\n",
    "        \n",
    "        return backtrack(0, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        le=len(num)\n",
    "        for p in range(1,le-1):\n",
    "            for q in range(p+1,le):\n",
    "                start,i,j=0,p,q\n",
    "                #count=0\n",
    "\n",
    "                while True:\n",
    "                    s1=num[start:i]\n",
    "                    if len(s1)>1 and s1[0]=='0': break\n",
    "                    x=int(s1)\n",
    "                    s2=num[i:j]\n",
    "                    \n",
    "                    if len(s2)>1 and s2[0]=='0': break\n",
    "\n",
    "                    y=int(s2)\n",
    "\n",
    "                    z=x+y\n",
    "                    #print(x,y,z)\n",
    "                    if j+len(str(z))>le:\n",
    "                        print('break')\n",
    "                        break\n",
    "                    if num[j:j+len(str(z))]==str(z):\n",
    "                        \n",
    "                        start,i,j=i,j,j+len(str(z))\n",
    "                        #print('=',start,i,j,le)\n",
    "                        if j==le: return True\n",
    "                    else:\n",
    "                        break\n",
    "                    #count+=1\n",
    "                    #if count>20: break\n",
    "        return False\n",
    "\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        if n < 3: return False \n",
    "        def bt(ss: str, v1: int, v2: int) -> bool:\n",
    "            m = len(ss)\n",
    "            if m == 0: return True \n",
    "            v3 = v1 + v2 \n",
    "            v3Str = str(v3)\n",
    "            u = len(v3Str)\n",
    "            if m >= u and ss[0: u] == v3Str: \n",
    "                return bt(ss[u:], v2, v3)\n",
    "            return False\n",
    "        v1 = 0\n",
    "        for i in range(n - 2):\n",
    "            if i != 0 and num[0] == '0': break \n",
    "            v1 = v1 * 10 + ord(num[i]) - ord('0')\n",
    "            v2 = 0\n",
    "            for j in range(i + 1, n - 1):\n",
    "                if j != i + 1 and num[i + 1] == '0': break \n",
    "                v2 = v2 * 10 + ord(num[j]) - ord('0')\n",
    "                v3 = v1 + v2 \n",
    "                kStr = num[j + 1:]\n",
    "                v3Str = str(v3)\n",
    "                p, u = len(v3Str), len(kStr)\n",
    "                if p > u: break \n",
    "                if kStr[0 : p] != v3Str: continue\n",
    "                if bt(num[j + 1 + p:], v2, v3): return True \n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        valid = False\n",
    "        def dfs(idx: int, prev: int, target: int):\n",
    "            nonlocal valid\n",
    "            if valid or idx == n:\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            number = 0\n",
    "            for jdx in range(idx, n):\n",
    "                if jdx > idx and num[idx] == \"0\":\n",
    "                    break\n",
    "                number = 10 * number + int(num[jdx])\n",
    "                if number == target:\n",
    "                    dfs(jdx + 1, target, prev + target)\n",
    "            return\n",
    "\n",
    "        firstNum = 0        \n",
    "        for first in range(n):\n",
    "            if valid or 2 * (first + 1) > n or (first > 0 and num[0] == \"0\"):\n",
    "                break\n",
    "\n",
    "            firstNum = 10 * firstNum + int(num[first])\n",
    "            secondNum = 0\n",
    "            for second in range(first + 1, n):\n",
    "                if valid or n - (second + 1) < max(first + 1, second - first) or (second > first + 1 and num[first + 1] == \"0\"):\n",
    "                    break\n",
    "                secondNum = 10 * secondNum + int(num[second])\n",
    "\n",
    "                target = firstNum + secondNum\n",
    "                dfs(second + 1, secondNum, target)\n",
    "\n",
    "        return valid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def check(i, j, k):\n",
    "            if j-i > 1 and num[i] == '0' or k-j > 1 and num[j] == '0':\n",
    "                return False\n",
    "            nxt = str(int(num[i:j]) + int(num[j:k]))\n",
    "            if not num[k:].startswith(nxt):\n",
    "                return k==n\n",
    "            return check(j, k, k+len(nxt))\n",
    "\n",
    "        n = len(num)\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if check(0, i, j):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        path = []\n",
    "        def backtrack(index):\n",
    "            if index == len(num) and len(path)>2:\n",
    "                return True\n",
    "            for i in range(index+1, len(num)+1):\n",
    "                if len(num[index:i]) > 1 and num[index]=='0':\n",
    "                    continue\n",
    "                if len(path) < 2:\n",
    "                    path.append(int(num[index:i]))\n",
    "                    if backtrack(i): return True\n",
    "                    path.pop()\n",
    "                elif int(num[index:i]) == path[-1] + path[-2]:\n",
    "                    path.append(int(num[index:i]))\n",
    "                    if backtrack(i): return True\n",
    "                    path.pop()\n",
    "            return False\n",
    "        return backtrack(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        ans = False\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                nonlocal ans\n",
    "                if len(path)>=3:\n",
    "                    ans=True\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s)) != s:\n",
    "                    break\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        ans = False\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                nonlocal ans\n",
    "                if len(path)>=3:\n",
    "                    ans=True\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s)) != s:\n",
    "                    break\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        def getThird(firstStart, firstEnd, secondStart, secondEnd):\n",
    "            num1 = int(num[firstStart: firstEnd+1])\n",
    "            num2 = int(num[secondStart: secondEnd+1])\n",
    "            return str(num1+num2)\n",
    "\n",
    "        def valid(secondStart, secondEnd):\n",
    "            firstStart, firstEnd = 0, secondStart-1\n",
    "            while secondEnd <= n-1:\n",
    "                third = getThird(firstStart, firstEnd, secondStart,secondEnd)\n",
    "                thirdStart, thirdEnd = secondEnd+1, secondEnd + len(third)\n",
    "                if thirdEnd>=n or num[thirdStart:thirdEnd+1] != third:\n",
    "                    return False\n",
    "                if thirdEnd==n-1:\n",
    "                    return True\n",
    "                firstStart, firstEnd = secondStart, secondEnd\n",
    "                secondStart, secondEnd = thirdStart, thirdEnd\n",
    "            return False  \n",
    "\n",
    "        for secondStart in range(1,n-1):\n",
    "            if num[0] == \"0\" and secondStart != 1:\n",
    "                break\n",
    "            for secondEnd in range(secondStart, n-1):\n",
    "                if num[secondStart] == \"0\" and secondEnd != secondStart:\n",
    "                    break \n",
    "                if valid(secondStart, secondEnd):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i>=n:\n",
    "                if len(path)>2:\n",
    "                    res[0] = True\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s)) != s:\n",
    "                  break\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "\n",
    "            return False\n",
    "        \n",
    "        res = [False]\n",
    "        dfs(0)\n",
    "        return res[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if len(path) >= 3 and path[-1] != path[-2] + path[-3]:\n",
    "                return False\n",
    "            if i == n:\n",
    "                return len(path) >= 3\n",
    "            if num[i] == '0':\n",
    "                path.append(int(num[i]))\n",
    "                if (dfs(i + 1)):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            else:\n",
    "                x = 0\n",
    "                for j in range(i, n):\n",
    "                    x = x * 10 + int(num[j])\n",
    "                    path.append(x)\n",
    "                    if dfs(j + 1):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        #if len(num) < 3:\n",
    "            #return False\n",
    "        self.ans = False\n",
    "        def dfs(i, start, count, num1, num2):\n",
    "            if self.ans == True:\n",
    "                return\n",
    "            if i >= len(num):\n",
    "                if i == start and count > 2:\n",
    "                    self.ans = True\n",
    "                return\n",
    "            # 判断当前是否是前置0\n",
    "            if num[start] == '0' and i != start:\n",
    "                return\n",
    "            if num1 == -1:\n",
    "                dfs(i + 1, i + 1, 1, int(num[start: i + 1]), -1)\n",
    "                dfs(i + 1, start, 0, -1, -1)\n",
    "                return\n",
    "            if num2 == -1:\n",
    "                dfs(i + 1, i + 1, 2, num1, int(num[start: i + 1]))\n",
    "                dfs(i + 1, start, 1, num1, -1)\n",
    "                return\n",
    "            if int(num[start: i + 1]) == num1 + num2:\n",
    "                dfs(i + 1, i + 1, count + 1, num2, int(num[start: i + 1]))\n",
    "            else:\n",
    "                dfs(i + 1, start, count, num1, num2)\n",
    "\n",
    "        dfs(0, 0, 0, -1, -1)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        ans = False\n",
    "        path = []\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                if len(path) >= 3:\n",
    "                    ans = True\n",
    "                return\n",
    "\n",
    "            for j in range(i, n):\n",
    "                c = int(num[i: j + 1])\n",
    "                if num[i] == '0' and c > 0:\n",
    "                    continue\n",
    "                if len(path) < 2:\n",
    "                    path.append(c)\n",
    "                    dfs(j + 1)\n",
    "                    path.pop()\n",
    "\n",
    "                if len(path) >= 2 and c == path[-1] + path[-2]:\n",
    "                    path.append(c)\n",
    "                    dfs(j + 1)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if len(path) >= 3 and path[-1] != path[-2] + path[-3]:\n",
    "                return False\n",
    "            if i == n:\n",
    "                return len(path) >= 3\n",
    "            if num[i] == '0':\n",
    "                path.append(int(num[i]))\n",
    "                if (dfs(i + 1)):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            else:\n",
    "                x = 0\n",
    "                for j in range(i, n):\n",
    "                    x = x * 10 + int(num[j])\n",
    "                    path.append(x)\n",
    "                    if dfs(j + 1):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "\n",
    "            return False\n",
    "        \n",
    "        return dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        if n < 3: return False\n",
    "        def check(p1, p2, j):\n",
    "            while j < n:\n",
    "                p = str(int(p1) + int(p2))\n",
    "                if num[j: j+len(p)] != p:\n",
    "                    return False\n",
    "                j += len(p)\n",
    "                p1, p2 = p2, p\n",
    "            return True\n",
    "        for i in range(1, n//2+1) if num[0] != \"0\" else [1]:\n",
    "            for j in range(i+1, n) if num[i] != \"0\" else [i+1]:\n",
    "                p1 = num[:i]\n",
    "                p2 = num[i:j]\n",
    "                if check(p1, p2, j):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "\n",
    "    # 回溯法来验证当前选择的数字是否能构成累加数\n",
    "        def backtrack(start, path):\n",
    "            # 如果序列大于3，并且已经遍历完整个字符串，则找到了累加序列\n",
    "            if len(path) >= 3 and start == length:\n",
    "                return True\n",
    "            \n",
    "            # 从start位置开始，尝试所有可能的数字\n",
    "            for end in range(start + 1, length + 1):\n",
    "                # 除0外，其他数字不应以0开始\n",
    "                if s[start] == \"0\" and end - start > 1:\n",
    "                    break\n",
    "                \n",
    "                num = int(s[start:end])\n",
    "                \n",
    "                # 如果path中的数字大于等于2，则需要验证当前数字是否为前两个数字的和\n",
    "                if len(path) >= 2:\n",
    "                    # 如果num大于path中最后两个数字的和，则不可能是累加序列\n",
    "                    if num > path[-1] + path[-2]:\n",
    "                        break\n",
    "                    # 如果num小于path中最后两个数字的和，则尝试下一个num\n",
    "                    elif num < path[-1] + path[-2]:\n",
    "                        continue\n",
    "                \n",
    "                # 回溯\n",
    "                path.append(num)\n",
    "                if backtrack(end, path):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            return False\n",
    "        \n",
    "        return backtrack(0, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        res = []\n",
    "        path = []\n",
    "        #### 因为你不知道从哪一步做这个切\n",
    "        ### 一个有效的 累加序列 必须 至少 包含 3 个数!!!\n",
    "\n",
    "        def dfs(i):\n",
    "            if i==len(num):\n",
    "                if len(path)>2:\n",
    "                    res.append(path.copy())\n",
    "                return\n",
    "            for j in range(i,len(num)):\n",
    "                n=num[i:j+1]\n",
    "                if str(int(n))!=n: break ### 整数才能跟整数做比较\n",
    "                if len(path)<2: path.append(int(n))\n",
    "                elif len(path)>=2 and int(n)==path[-1]+path[-2]:\n",
    "                    path.append(int(n))\n",
    "                else:\n",
    "                    continue ### 换字符串，同层continue 相当于替换字符 ## 这里就不进下一步\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return len(res)>0 \n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "        # def backtracking(start):\n",
    "        #     if start == len(num):\n",
    "        #         if len(path) > 2:\n",
    "        #             res.append(path[:])\n",
    "        #             print(\"res\",res)\n",
    "        #         return\n",
    "        #     for i in range(start, len(num)):\n",
    "        #         n = num[start: i + 1]\n",
    "        #         if str(int(n)) != n:\n",
    "        #             break\n",
    "        #         if len(path) < 2:\n",
    "        #             path.append(int(n))\n",
    "        #         elif len(path) >= 2 and int(n) == path[-1] + path[-2]:\n",
    "        #             path.append(int(n))\n",
    "        #         else:\n",
    "        #             continue ### 这里都不符合，就要继续，而不是break掉，类似于，探索下一个可能的数字 发现1+9 不等于9，在同层循环里继续1+99（在同一层里增加i）！！！ 这个continue 非常重要，他就是会一直枚举\n",
    "        #         print(path)\n",
    "        #         backtracking(i + 1)\n",
    "        #         path.pop()\n",
    "        \n",
    "        # backtracking(0)\n",
    "        # return len(res) > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        flag = False\n",
    "        def dfs(u, st):\n",
    "            nonlocal flag\n",
    "            if u == n:\n",
    "                if len(ans) >= 3:\n",
    "                    flag = True\n",
    "                return\n",
    "            if u - st + 1 >= 2 and num[st] == '0':\n",
    "                return\n",
    "            if u < n - 1:\n",
    "                dfs(u + 1, st)\n",
    "            a = int(num[st:u+1])\n",
    "            if len(ans) >= 2 and ans[-1] + ans[-2] != a:\n",
    "                return\n",
    "            ans.append(a)\n",
    "            dfs(u + 1, u + 1)\n",
    "            ans.pop()\n",
    "        dfs(0, 0)\n",
    "        return flag\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.nums = []\n",
    "    def checkNum(self, num):\n",
    "        if num[0]=='0' and len(num) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    def dfs(self,num,start):\n",
    "        if len(self.nums) >= 3:\n",
    "            if self.nums[-1] != self.nums[-2] + self.nums[-3]:\n",
    "                return False\n",
    "            if start == len(num):\n",
    "                return True\n",
    "        for end in range(start,len(num)):\n",
    "            curStr = num[start:end+1]\n",
    "            if not self.checkNum(curStr):\n",
    "                continue\n",
    "            self.nums.append(int(curStr))\n",
    "            if self.dfs(num, end + 1):\n",
    "                return True\n",
    "            self.nums.pop()\n",
    "        return False\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        return self.dfs(num, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        ans = False\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                if len(path)>=3:\n",
    "                    ans = True\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s))!= s:\n",
    "                    break\n",
    "                if len(path)>=2:\n",
    "                    if path[-1]+ path[-2] !=int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)         \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        ans = False\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                nonlocal ans\n",
    "                if len(path)>=3:\n",
    "                    ans=True\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s)) != s:\n",
    "                    break\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "\n",
    "        self.ans = False\n",
    "        def dfs(i, start, count, num1, num2):\n",
    "            if self.ans == True:\n",
    "                return\n",
    "            if i >= len(num):\n",
    "                # 判断当前划分数字数量是否至少有3个\n",
    "                if i == start and count > 2:\n",
    "                    self.ans = True\n",
    "                return\n",
    "            # 判断当前是否是前置0\n",
    "            if num[start] == '0' and i != start:\n",
    "                return\n",
    "            if num1 == -1:\n",
    "                dfs(i + 1, i + 1, 1, int(num[start: i + 1]), -1)\n",
    "                dfs(i + 1, start, 0, -1, -1)\n",
    "                return\n",
    "            if num2 == -1:\n",
    "                dfs(i + 1, i + 1, 2, num1, int(num[start: i + 1]))\n",
    "                dfs(i + 1, start, 1, num1, -1)\n",
    "                return\n",
    "            if int(num[start: i + 1]) == num1 + num2:\n",
    "                dfs(i + 1, i + 1, count + 1, num2, int(num[start: i + 1]))\n",
    "            else:\n",
    "                dfs(i + 1, start, count, num1, num2)\n",
    "\n",
    "        dfs(0, 0, 0, -1, -1)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def check(a, b):\n",
    "            if (a.startswith(\"0\") and a != \"0\") or (b.startswith(\"0\") and b != \"0\"):\n",
    "                return False\n",
    "            temp = a + b\n",
    "            a, b = b, str(int(b) + int(a))\n",
    "            temp += b\n",
    "            while len(temp) < len(num):\n",
    "                a, b = b, str(int(b) + int(a))\n",
    "                temp += b\n",
    "            return num == temp\n",
    "\n",
    "        for j in range(1, len(num) - 1):\n",
    "            for i in range(j):\n",
    "                if check(num[: i + 1], num[i + 1 : j + 1]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def Additive(num: str, st: str, ed: str, prelen: int) -> bool:\n",
    "            next = str(int(st) + int(ed))\n",
    "            n1, n2, n3 = len(st), len(ed), len(next)\n",
    "            if prelen + n1 + n2 + n3 > len(num): return False\n",
    "            if num[prelen + n1 + n2 : prelen + n1 + n2 + n3] == next:\n",
    "                if prelen + n1 + n2 + n3 == len(num): return True\n",
    "                else: return Additive(num, ed, next, prelen + n1)\n",
    "            else: return False\n",
    "        n = len(num)\n",
    "        for i in range(n):\n",
    "            st = num[:i+1]\n",
    "            if len(st) > 1 and st[0] == '0': continue\n",
    "            for j in range(i + 1, n):\n",
    "                ed = num[i + 1 : j + 1]\n",
    "                if len(ed) > 1 and ed[0] == '0': continue\n",
    "                ans = Additive(num, st, ed, 0)\n",
    "                if ans: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        le=len(num)\n",
    "        for p in range(1,le-1):\n",
    "            for q in range(p+1,le):\n",
    "                start,i,j=0,p,q\n",
    "                #count=0\n",
    "\n",
    "                while True:\n",
    "                    s1=num[start:i]\n",
    "                    if len(s1)>1 and s1[0]=='0': break\n",
    "                    x=int(s1)\n",
    "                    s2=num[i:j]\n",
    "                    print('i,j,s2:',i,j,s2)\n",
    "                    if len(s2)>1 and s2[0]=='0': break\n",
    "                    try:\n",
    "                        y=int(s2)\n",
    "                    except:\n",
    "                        print('s2=',s2)\n",
    "                        return False\n",
    "                    z=x+y\n",
    "                    print(x,y,z)\n",
    "                    if j+len(str(z))>le:\n",
    "                        print('break')\n",
    "                        break\n",
    "                    if num[j:j+len(str(z))]==str(z):\n",
    "                        \n",
    "                        start,i,j=i,j,j+len(str(z))\n",
    "                        print('=',start,i,j,le)\n",
    "                        if j==le: return True\n",
    "                    else:\n",
    "                        break\n",
    "                    #count+=1\n",
    "                    #if count>20: break\n",
    "        return False\n",
    "\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        if n<3:\n",
    "            return False\n",
    "        def dfs(p1,p2,j):\n",
    "            while j<n:\n",
    "                p=str(int(p1)+int(p2))\n",
    "                if num[j:j+len(p)]!=p:\n",
    "                    return False\n",
    "                j+=len(p)\n",
    "                p1,p2=p2,p\n",
    "            return True\n",
    "        \n",
    "        for i in range(1,n//2+1) if num[0]!='0' else [1]:\n",
    "            for j in range(i+1,n) if num[i]!='0' else [i+1]:\n",
    "                p1=num[:i]\n",
    "                p2=num[i:j]\n",
    "                if dfs(p1,p2,j):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        path = []\n",
    "        if len(num)<3:\n",
    "            return False\n",
    "        def huisu(idx):\n",
    "            if len(path)>=3 and path[-1]!=path[-2]+path[-3]:\n",
    "                return False\n",
    "            if idx == len(num):\n",
    "                return len(path)>=3\n",
    "            if num[idx] == '0':\n",
    "                path.append(0)\n",
    "                if huisu(idx+1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            else:\n",
    "                x = 0\n",
    "                for i in range(idx,len(num)):\n",
    "                    x = x*10+int(num[i])\n",
    "                    path.append(x)\n",
    "                    if huisu(i+1):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "            return False\n",
    "        return huisu(0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        ans = False\n",
    "        path = []\n",
    "\n",
    "        # def valid(s, path):\n",
    "        #     path = [0] + path + [len(s)]\n",
    "        #     nums = []\n",
    "        #     for i in range(len(path) - 1):\n",
    "        #         t = s[path[i]:path[i+1]]\n",
    "        #         if len(t) > 1 and t[0] == '0':\n",
    "        #             return False\n",
    "        #         if t:\n",
    "        #             nums.append(int(t))\n",
    "            \n",
    "        #     if len(nums) <= 2:\n",
    "        #         return False\n",
    "        #     for i in range(2, len(nums)):\n",
    "        #         if nums[i-2] + nums[i-1] != nums[i]:\n",
    "        #             return False\n",
    "        #     # print(nums, f)\n",
    "        #     return True\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                # print(path)\n",
    "                if len(path) >= 3:\n",
    "                    ans = True\n",
    "                return \n",
    "\n",
    "            for j in range(i, n):\n",
    "                if j != i and num[i] == '0':\n",
    "                    continue\n",
    "\n",
    "                digit = int(num[i:j+1])\n",
    "\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != digit:\n",
    "                        continue\n",
    "\n",
    "                path.append(digit)\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        res = []\n",
    "        path = []\n",
    "        \n",
    "        def backtracking(start):\n",
    "            if start == len(num):\n",
    "                if len(path) > 2:\n",
    "                    res.append(path[:])\n",
    "                return\n",
    "            for i in range(start, len(num)):\n",
    "                n = num[start: i + 1]\n",
    "                if str(int(n)) != n:\n",
    "                    break\n",
    "                if len(path) < 2:\n",
    "                    path.append(int(n))\n",
    "                elif len(path) >= 2 and int(n) == path[-1] + path[-2]:\n",
    "                    path.append(int(n))\n",
    "                else:\n",
    "                    continue\n",
    "                backtracking(i + 1)\n",
    "                path.pop()\n",
    "        \n",
    "        backtracking(0)\n",
    "        return len(res) > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        res = False\n",
    "        path = []\n",
    "        n = len(num)\n",
    "\n",
    "        def dfs(i, start):\n",
    "            nonlocal res\n",
    "            if i == n:\n",
    "                if len(path) >= 3:\n",
    "                    res = True\n",
    "                return\n",
    "\n",
    "            if i - start > 0 and num[start] == '0':\n",
    "                return                \n",
    "            \n",
    "            if i < n - 1:\n",
    "                dfs(i + 1, start)\n",
    "\n",
    "            cur = int(num[start: i + 1])\n",
    "            if len(path) < 2 or cur == path[-1] + path[-2]:\n",
    "                path.append(cur)\n",
    "                dfs(i + 1, i + 1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        if num[0]=='0' and len(num)<3:\n",
    "            return False\n",
    "        for i in range(1,len(num)):\n",
    "            for j in range(i+1,len(num)):\n",
    "                t1=int(num[:i]) #t1为i\n",
    "                t2=int(num[i:j])\n",
    "                if len(num[i:j])>1 and num[i]=='0' or len(num[:i])>1 and num[0] =='0':#前数为0，后数为两位数，则继续寻找下一个\n",
    "                    break\n",
    "                tstr=num[:j] #前数\n",
    "                while num[len(tstr):].find(str(t1+t2))==0:\n",
    "                    tstr+=str(t1+t2)\n",
    "                    t1,t2=t2,t1+t2\n",
    "                if len(tstr)==len(num):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        def getThird(firstStart, firstEnd, secondStart, secondEnd):\n",
    "            num1 = eval(num[firstStart: firstEnd+1])\n",
    "            num2 = eval(num[secondStart: secondEnd+1])\n",
    "            return str(num1+num2)\n",
    "\n",
    "        def valid(secondStart, secondEnd):\n",
    "            firstStart, firstEnd = 0, secondStart-1\n",
    "            while secondEnd <= n-1:\n",
    "                third = getThird(firstStart, firstEnd, secondStart,secondEnd)\n",
    "                thirdStart, thirdEnd = secondEnd+1, secondEnd + len(third)\n",
    "                if thirdEnd>=n or num[thirdStart:thirdEnd+1] != third:\n",
    "                    return False\n",
    "                if thirdEnd==n-1:\n",
    "                    return True\n",
    "                firstStart, firstEnd = secondStart, secondEnd\n",
    "                secondStart, secondEnd = thirdStart, thirdEnd\n",
    "            return False  \n",
    "\n",
    "        for secondStart in range(1,n-1):\n",
    "            if num[0] == \"0\" and secondStart != 1:\n",
    "                break\n",
    "            for secondEnd in range(secondStart, n-1):\n",
    "                if num[secondStart] == \"0\" and secondEnd != secondStart:\n",
    "                    break \n",
    "                if valid(secondStart, secondEnd):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        total_len = len(num)\n",
    "\n",
    "        def check_valid(v1, v2, idx):\n",
    "            su = v1 + v2\n",
    "            ssu = str(su)\n",
    "            end = idx + len(ssu)\n",
    "            if end > total_len:\n",
    "                return False\n",
    "            p3 = num[idx: end]\n",
    "            if p3 == ssu:\n",
    "                if total_len == end:\n",
    "                    return True\n",
    "                return check_valid(v2, su, end)\n",
    "            return False\n",
    "        mem = {}\n",
    "\n",
    "        def get_num(a, b):\n",
    "            if mem.get((a,b)):\n",
    "                return False\n",
    "            mem[(a,b)] = True\n",
    "\n",
    "            rest_len = total_len - a - b\n",
    "            if rest_len < a or rest_len < b:\n",
    "                return False\n",
    "                \n",
    "            v1 = num[:a]\n",
    "            v2 = num[a:a + b]\n",
    "\n",
    "            if v1 != \"0\" and v1.startswith(\"0\"):\n",
    "                return False\n",
    "            if v2 != \"0\" and v2.startswith(\"0\"):\n",
    "                return False\n",
    "\n",
    "            iv1 = int(v1)\n",
    "            iv2 = int(v2)\n",
    "\n",
    "            if check_valid(iv1, iv2, a + b):\n",
    "                return True\n",
    "\n",
    "            if get_num(a + 1, b):\n",
    "                return True\n",
    "\n",
    "            if get_num(a, b + 1):\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return get_num(1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        #看成枚举,\n",
    "        n=len(num)\n",
    "        path=[]\n",
    "        ans=False\n",
    "        def dfs(i:int)->None:\n",
    "            if len(path)>=3:\n",
    "                if path[-1]!=path[-2]+path[-3]:\n",
    "                    return\n",
    "            nonlocal ans\n",
    "            if i==n:\n",
    "                m=len(path)\n",
    "                if m<3:\n",
    "                    return\n",
    "                for i,(x,y) in enumerate(zip(path,path[1:-1])):\n",
    "                    if path[i+2]!=x+y:\n",
    "                        return  \n",
    "                ans=True\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                if j-i+1>1 and num[i]=='0':\n",
    "                    continue\n",
    "                path.append(int(num[i:j+1]))\n",
    "                dfs(j+1)\n",
    "                path.pop()  \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\r\n",
    "        n = len(num)\r\n",
    "\r\n",
    "        def check(pre_0, pre_1, s):\r\n",
    "            # print(pre_0, pre_1, s)\r\n",
    "            if not s:\r\n",
    "                return True\r\n",
    "            prefix = str(int(pre_0) + int(pre_1))\r\n",
    "            if not s.startswith(prefix):\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return check(pre_1, prefix, s[len(prefix):])\r\n",
    "        \r\n",
    "        for i in range(1, n):\r\n",
    "            pre_0 = num[:i]\r\n",
    "            if i > 1 and num[0] == '0':\r\n",
    "                break\r\n",
    "            for j in range(i + 1, n):\r\n",
    "                if n - j < i or n - j < j - i:\r\n",
    "                    break\r\n",
    "                if j - i > 1 and num[i] == '0':\r\n",
    "                    break\r\n",
    "                pre_1 = num[i: j]\r\n",
    "                if check(pre_0, pre_1, num[j:]):\r\n",
    "                    return True\r\n",
    "        return False\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        total_len = len(num)\n",
    "\n",
    "        def check_valid(v1, v2, idx):\n",
    "            su = v1 + v2\n",
    "            ssu = str(su)\n",
    "            if idx + len(ssu) > total_len:\n",
    "                return False\n",
    "            p3 = num[idx: idx + len(ssu)]\n",
    "            if p3 == ssu:\n",
    "                if total_len == idx + len(ssu):\n",
    "                    return True\n",
    "                return check_valid(v2, su, idx + len(ssu))\n",
    "            return False\n",
    "\n",
    "        def get_num(a, b):\n",
    "            if a + b > (total_len // 3 * 2 + (total_len % 3 and 1)):\n",
    "                return False\n",
    "            v1 = num[:a]\n",
    "            v2 = num[a:a + b]\n",
    "\n",
    "            if v1 != \"0\" and v1.startswith(\"0\"):\n",
    "                return False\n",
    "            if v2 != \"0\" and v2.startswith(\"0\"):\n",
    "                return False\n",
    "\n",
    "            iv1 = int(v1)\n",
    "            iv2 = int(v2)\n",
    "\n",
    "            if check_valid(iv1, iv2, a + b):\n",
    "                return True\n",
    "\n",
    "            if get_num(a + 1, b):\n",
    "                return True\n",
    "\n",
    "            if get_num(a, b + 1):\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return get_num(1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        ans = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                if len(path) > 2:\n",
    "                    ans.append(path[:])\n",
    "                return\n",
    "            m = len(path)\n",
    "            for j in range(i, n):\n",
    "                if j - i > 0 and num[i] == '0':\n",
    "                    continue\n",
    "                digit = int(num[i:j+1])\n",
    "                if m <= 2 or digit == path[m-1] + path[m-2]:\n",
    "                    path.append(digit)\n",
    "                    dfs(j + 1)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        for v in ans:\n",
    "            flag = False\n",
    "            for i in range(2, len(v)):\n",
    "                if v[i] != v[i-1] + v[i-2]:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        def backtrack(startidx, path, curlen):\n",
    "            if len(path)>=3 and path[-1] == path[-2]+path[-3] and curlen ==n:\n",
    "                res.append(path)\n",
    "                return None\n",
    "            if startidx>=n:\n",
    "                return None\n",
    "            if num[startidx]=='0':\n",
    "                if len(path)<2 or (len(path)>=2 and path[-1]+path[-2]==0):\n",
    "                    backtrack(startidx+1, path+[0], curlen+1)\n",
    "\n",
    "            for i in range(startidx, n):\n",
    "                if num[startidx]=='0':\n",
    "                    continue\n",
    "                cur_num = int(num[startidx:i+1])\n",
    "                if len(path)>=2 and cur_num == path[-1]+path[-2]:\n",
    "                    backtrack(i+1, path+[cur_num], curlen+i+1-startidx)\n",
    "                elif len(path)<2:\n",
    "                    backtrack(i+1, path+[cur_num], curlen+i+1-startidx)\n",
    "\n",
    "        res = []\n",
    "        backtrack(0,[],0)\n",
    "        # print(res)\n",
    "        return True if res else False   \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i>=n:\n",
    "                nonlocal res\n",
    "                if len(path)>2:\n",
    "                    res = True\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s)) != s:\n",
    "                  break\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "\n",
    "            return False\n",
    "        \n",
    "        res = False\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def dfs(num, firstnum, secondnum):\n",
    "            if not num: return True\n",
    "            total = firstnum + secondnum\n",
    "            length = len(str(total))\n",
    "            if str(total) == num[:length]:\n",
    "                return dfs(num[length:], secondnum, total)\n",
    "            return False\n",
    "        \n",
    "        for i in range(1, len(num)-1):\n",
    "            if num[0] == '0' and i > 1: break\n",
    "            for j in range(i+1, len(num)):\n",
    "                if j-i > 1 and num[i] == '0': break\n",
    "                if dfs(num[j:], int(num[:i]), int(num[i:j])): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        if num is None or len(num) < 3:\n",
    "            return False\n",
    "        first = ''\n",
    "        second = ''\n",
    "        thrid = ''\n",
    "        n = len(num)\n",
    "        zeroFlag = False\n",
    "        if num[0] == '0' and num[1] == '0':\n",
    "            zeroFlag =True\n",
    "            for i in range(2, n):\n",
    "                if num[i] != '0':\n",
    "                    return False\n",
    "        elif num[0] == '0':\n",
    "            first = '0'\n",
    "            for i in range(2, n):\n",
    "                second = num[1:i]\n",
    "                thrid = second\n",
    "                if self.dfs(second, thrid, num, i):\n",
    "                    return True\n",
    "        else:\n",
    "            for i in range(1, n + 1):\n",
    "                for j in range(i + 1, n):\n",
    "                    first = num[0:i]\n",
    "                    second = num[i:j]\n",
    "                    if len(second) > 1 and second[0] == '0':\n",
    "                        break\n",
    "                    thrid = self.getTarget(first, second)\n",
    "                    if self.dfs(second, thrid, num, j):\n",
    "                        return True\n",
    "        return zeroFlag\n",
    "\n",
    "    def dfs(self, second: str, thrid: str, num: str, index: int):\n",
    "        if index == len(num):\n",
    "            return True\n",
    "        lens = len(thrid)\n",
    "        if index + lens > len(num):\n",
    "            return False\n",
    "        subStr = num[index: index + lens]\n",
    "        if thrid == subStr:\n",
    "            return self.dfs(thrid, self.getTarget(second, thrid), num, index + lens)\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def getTarget(self, num1: str, num2: str):\n",
    "\n",
    "        res = list()\n",
    "        carry = 0\n",
    "        i = len(num1) - 1\n",
    "        j = len(num2) - 1\n",
    "        while i >= 0 or j >= 0 or carry != 0:\n",
    "            if i >= 0:\n",
    "                carry += ord(num1[i]) - ord('0')\n",
    "                i -= 1\n",
    "            if j >= 0:\n",
    "                carry += ord(num2[j]) - ord('0')\n",
    "                j -= 1\n",
    "                \n",
    "            \n",
    "            res.append(str(carry % 10))\n",
    "            carry = (int)(carry / 10)\n",
    "            \n",
    "        res.reverse()\n",
    "        result = ''.join(res)\n",
    "       \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.num_l=[]\n",
    "        self.ret=False\n",
    "    def sub(self,num):\n",
    "        if len(self.num_l)>=3:\n",
    "            if int(self.num_l[-1])!=int(self.num_l[-2])+int(self.num_l[-3]):\n",
    "                return\n",
    "        if self.ret:\n",
    "            return\n",
    "        if len(num)==0:\n",
    "            if len(self.num_l)<3:\n",
    "                return\n",
    "            n_l = [int(i) for i in self.num_l]\n",
    "            for i in range(2,len(n_l)):\n",
    "                if n_l[i]!=n_l[i-1]+n_l[i-2]:\n",
    "                    return\n",
    "            self.ret = True\n",
    "        else:\n",
    "            end = 2 if num[0]=='0' else len(num)+1\n",
    "            for i in range(1,end):\n",
    "                l1,l2=num[0:i],num[i:]\n",
    "                self.num_l.append(l1)\n",
    "                self.sub(l2)\n",
    "                self.num_l.pop()\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        self.sub(num)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        ans = False\n",
    "        path = []\n",
    "        n = len(num)\n",
    "\n",
    "        def dfs(i: int, start: int) -> None:\n",
    "            if len(path) >= 3: # 检查是否合法\n",
    "                if path[-1] !=path[-2] + path[-3]:\n",
    "                    return \n",
    "            \n",
    "            nonlocal ans\n",
    "            if ans:\n",
    "                return\n",
    "            \n",
    "            if i == n:\n",
    "                if len(path) >= 3: # 枚举到末尾，如果长度大于3，则认为查找到答案\n",
    "                    ans = True  \n",
    "                return # 这里return不能忘，也不能缩进到上面那个if里面，否则报错 IndexError: string index out of range if len(t) != 1 and t[0] == '0': # 去除枚举到前导0的情况\n",
    "            # 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）\n",
    "            if i < n - 1:\n",
    "                dfs(i + 1, start)\n",
    "\n",
    "            # 选 i 和 i+1 之间的逗号（把 num[i] 作为子串的最后一个字符）\n",
    "            t = num[start: i+1]\n",
    "\n",
    "            if len(t)!=1 and t[0] == '0': # 去除枚举到前导0的情况\n",
    "                return\n",
    "            cur = int(t)\n",
    "            path.append(cur) # 选中这个分割点，继续枚举\n",
    "            dfs(i+1,i+1)\n",
    "            path.pop() \n",
    "\n",
    "        dfs(0, 0)\n",
    "        \n",
    "        return ans\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        path = [] # 存储分割得到的数字\n",
    "        ans = False \n",
    "        n = len(num)\n",
    "\n",
    "        def dfs(i,start): \n",
    "            if len(path) >= 3: #检查是否合法\n",
    "                if path[-1] !=path[-2]+path[-3]:\n",
    "                    return \n",
    "            nonlocal ans\n",
    "            if ans: #减枝 如果已经找到可行分割方案，不需要继续查找\n",
    "                return\n",
    "            if i == n:\n",
    "                if len(path) >=3: #枚举到末尾，如果长度大于3，则认为查找到答案\n",
    "                    ans = True\n",
    "                return\n",
    "            if i < n-1: # n个字符，中间最多n-1个逗号\n",
    "                dfs(i+1,start)\n",
    "            t = num[start:i+1]\n",
    "            if len(t)!=1 and t[0] == '0': #去除枚举到前导0的情况\n",
    "                return\n",
    "            cur = int(t)\n",
    "            path.append(cur) #选中这个分割点，继续枚举\n",
    "            dfs(i+1,i+1)\n",
    "            path.pop() \n",
    "        dfs(0,0)\n",
    "        return ans\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        def check(i, j, k):\n",
    "            if j-i > 1 and num[i] == '0' or k-j > 1 and num[j] == '0':\n",
    "                return False\n",
    "            nxt = str(int(num[i:j]) + int(num[j:k]))\n",
    "            print(i, j, k, nxt)\n",
    "            if not num[k:].startswith(nxt):\n",
    "                return k==n\n",
    "            return check(j, k, k+len(nxt))\n",
    "\n",
    "        n = len(num)\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1, n):\n",
    "                print(i,j)\n",
    "                if check(0, i, j):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                nonlocal res\n",
    "                if len(path)>2:\n",
    "                    res = True\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                s = num[i:j+1]\n",
    "                if str(int(s)) != s:\n",
    "                  break\n",
    "                if len(path) >= 2:\n",
    "                    if path[-1] + path[-2] != int(s):\n",
    "                        continue\n",
    "                path.append(int(s))\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "\n",
    "            return False\n",
    "        \n",
    "        res = False\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "\n",
    "        self.ans = False\n",
    "        def dfs(i, start, count, num1, num2):\n",
    "            if self.ans == True:\n",
    "                return\n",
    "            if i >= len(num):\n",
    "                # 判断当前划分数字数量是否至少有3个\n",
    "                if i == start and count > 2:\n",
    "                    self.ans = True\n",
    "                return\n",
    "            # 判断当前是否是前置0\n",
    "            if num[start] == '0' and i != start:\n",
    "                return\n",
    "            if num1 == -1:\n",
    "                dfs(i + 1, i + 1, 1, int(num[start: i + 1]), -1)\n",
    "                dfs(i + 1, start, 0, -1, -1)\n",
    "                return\n",
    "            if num2 == -1:\n",
    "                dfs(i + 1, i + 1, 2, num1, int(num[start: i + 1]))\n",
    "                dfs(i + 1, start, 1, num1, -1)\n",
    "                return\n",
    "            if int(num[start: i + 1]) == num1 + num2:\n",
    "                dfs(i + 1, i + 1, count + 1, num2, int(num[start: i + 1]))\n",
    "            else:\n",
    "                dfs(i + 1, start, count, num1, num2)\n",
    "\n",
    "        dfs(0, 0, 0, -1, -1)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAdditiveNumber(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        if n < 3: return False\n",
    "        ans = False\n",
    "        path = []\n",
    "\n",
    "        # 选或不选\n",
    "        def f(i: int, start: int) -> None:\n",
    "            nonlocal ans\n",
    "            if i == n or ans:\n",
    "                if len(path) > 2:\n",
    "                    ans = True\n",
    "                return\n",
    "            \n",
    "            if i < n - 1:\n",
    "                f(i + 1, start)\n",
    "            \n",
    "            t = num[start : i + 1]\n",
    "            if len(t) > 1 and num[start] == \"0\":\n",
    "                return\n",
    "            elif len(path) < 2 or int(t) == path[-1] + path[-2]:\n",
    "                path.append(int(t))\n",
    "                f(i + 1, i + 1)\n",
    "                if ans:\n",
    "                    return\n",
    "                path.pop()\n",
    "            elif len(path) >= 2 and int(t) > path[-1] + path[-2]:\n",
    "                return\n",
    "        \n",
    "        # 选哪个\n",
    "        # def f(i: int) -> None:\n",
    "        #     nonlocal ans\n",
    "        #     if i == n or ans:\n",
    "        #         if len(path) > 2:\n",
    "        #             ans = True\n",
    "        #         return\n",
    "            \n",
    "        #     for j in range(i, n):\n",
    "        #         t = num[i : j + 1]\n",
    "        #         if len(t) > 1 and num[i] == \"0\":\n",
    "        #             break\n",
    "        #         elif len(path) < 2 or int(t) == path[-1] + path[-2]:\n",
    "        #             path.append(int(t))\n",
    "        #             f(j + 1)\n",
    "        #             if ans:\n",
    "        #                 return\n",
    "        #             path.pop()\n",
    "        #         elif len(path) >= 2 and int(t) > path[-1] + path[-2]:\n",
    "        #             break\n",
    "        #     return\n",
    "        f(0, 0)\n",
    "        return ans\n",
    "                    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
